package leetcode.editor.cn.q1xx

import leetcode.editor.cn.TreeNode
import java.util.*

class Q112 {

    fun hasPathSum(root: TreeNode?, targetSum: Int): Boolean {
        if (root == null)
            return false
        val stack = LinkedList<Pair<TreeNode, Int>>()
        stack.push(root to root.`val`)
        while (stack.isNotEmpty()) {
            val (curNode, curSum) = stack.pop()
            if (curSum == targetSum && curNode.left == null && curNode.right == null) return true
            if (curNode.left != null)
                stack.push(curNode.left!! to curNode.left!!.`val` + curSum)
            if (curNode.right != null) {
                stack.push(curNode.right!! to curNode.right!!.`val` + curSum)
            }
        }
        return false
    }

}